package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 2020/12/27 下午8:38
 *
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */
public class _84_柱状图中最大的矩形_03 {

    public int largestRectangleArea(int[] heights) {

        if (heights == null || heights.length == 0) {

            return 0;
        }

        int[] leftToRight = new int[heights.length];

        for (int i = 0; i < heights.length; i++) {

            leftToRight[i] =  -1;
        }

        int max = 0;
        /**
         * from left to right
         */

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < heights.length; i++) {

            if (stack.isEmpty()) {

                stack.push(i);
                continue;
            }

            int index;
            while (!stack.isEmpty() && (heights[index = stack.peek()] > heights[i])) {

                max = Math.max(max, heights[index] *(i - leftToRight[index] - 1));
                stack.pop();
            }

            if (!stack.isEmpty()) {

                leftToRight[i] = stack.peek();
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {

            Integer index = stack.pop();
            max = Math.max(max,heights[index] *(heights.length - leftToRight[index] - 1));
        }

        return max;
    }
}
